#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

// 1. 对撞指针示例：两数之和（有序数组）
class TwoSum {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0, right = numbers.size() - 1;
        
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return {left + 1, right + 1}; // 返回1-indexed位置
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return {}; // 未找到
    }
};

// 2. 对撞指针示例：盛最多水的容器
class ContainerWithMostWater {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int maxWater = 0;
        
        while (left < right) {
            int currentArea = min(height[left], height[right]) * (right - left);
            maxWater = max(maxWater, currentArea);
            
            // 移动较短的边，因为移动较长的边不会增加面积
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        
        return maxWater;
    }
};

// 3. 快慢指针示例：移除重复元素
class RemoveDuplicates {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;
        
        int slow = 0;
        for (int fast = 1; fast < nums.size(); fast++) {
            if (nums[fast] != nums[slow]) {
                slow++;
                nums[slow] = nums[fast];
            }
        }
        
        return slow + 1; // 返回新数组长度
    }
};

// 4. 滑动窗口示例：最长无重复字符子串
class LongestSubstringWithoutRepeating {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> charMap(128, -1); // ASCII字符映射
        int left = 0, maxLen = 0;
        
        for (int right = 0; right < s.length(); right++) {
            char c = s[right];
            
            // 如果字符已存在且在当前窗口内
            if (charMap[c] >= left) {
                left = charMap[c] + 1; // 移动左指针
            }
            
            charMap[c] = right; // 更新字符位置
            maxLen = max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
};

// 5. 滑动窗口示例：最小覆盖子串
class MinimumWindowSubstring {
public:
    string minWindow(string s, string t) {
        vector<int> need(128, 0);
        int needCount = t.length();
        
        // 统计t中每个字符的需求量
        for (char c : t) {
            need[c]++;
        }
        
        int left = 0, right = 0;
        int start = 0, minLen = INT_MAX;
        
        while (right < s.length()) {
            char c = s[right];
            
            // 扩展窗口
            if (need[c] > 0) {
                needCount--;
            }
            need[c]--;
            right++;
            
            // 收缩窗口
            while (needCount == 0) {
                if (right - left < minLen) {
                    minLen = right - left;
                    start = left;
                }
                
                char d = s[left];
                need[d]++;
                if (need[d] > 0) {
                    needCount++;
                }
                left++;
            }
        }
        
        return minLen == INT_MAX ? "" : s.substr(start, minLen);
    }
};

// 6. 三数之和（对撞指针的扩展应用）
class ThreeSum {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        
        for (int i = 0; i < nums.size() - 2; i++) {
            // 跳过重复元素
            if (i > 0 && nums[i] == nums[i-1]) continue;
            
            int left = i + 1, right = nums.size() - 1;
            int target = -nums[i];
            
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == target) {
                    result.push_back({nums[i], nums[left], nums[right]});
                    
                    // 跳过重复元素
                    while (left < right && nums[left] == nums[left+1]) left++;
                    while (left < right && nums[right] == nums[right-1]) right--;
                    
                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        return result;
    }
};

// 演示函数
void demonstrateTwoPointers() {
    cout << "=== 双指针算法演示 ===" << endl << endl;
    
    // 1. 两数之和演示
    cout << "1. 两数之和（有序数组）:" << endl;
    vector<int> numbers = {2, 7, 11, 15};
    int target = 9;
    TwoSum twoSum;
    vector<int> result = twoSum.twoSum(numbers, target);
    cout << "数组: [2, 7, 11, 15], 目标: " << target << endl;
    cout << "结果: [" << result[0] << ", " << result[1] << "]" << endl << endl;
    
    // 2. 盛最多水的容器演示
    cout << "2. 盛最多水的容器:" << endl;
    vector<int> height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    ContainerWithMostWater container;
    int maxArea = container.maxArea(height);
    cout << "高度数组: [1, 8, 6, 2, 5, 4, 8, 3, 7]" << endl;
    cout << "最大面积: " << maxArea << endl << endl;
    
    // 3. 移除重复元素演示
    cout << "3. 移除重复元素:" << endl;
    vector<int> nums = {1, 1, 2, 2, 3, 4, 4, 5};
    RemoveDuplicates removeDup;
    int newLength = removeDup.removeDuplicates(nums);
    cout << "原数组: [1, 1, 2, 2, 3, 4, 4, 5]" << endl;
    cout << "新数组长度: " << newLength << endl;
    cout << "新数组: [";
    for (int i = 0; i < newLength; i++) {
        cout << nums[i];
        if (i < newLength - 1) cout << ", ";
    }
    cout << "]" << endl << endl;
    
    // 4. 最长无重复字符子串演示
    cout << "4. 最长无重复字符子串:" << endl;
    string s = "abcabcbb";
    LongestSubstringWithoutRepeating longestSub;
    int maxLength = longestSub.lengthOfLongestSubstring(s);
    cout << "字符串: \"" << s << "\"" << endl;
    cout << "最长无重复子串长度: " << maxLength << endl << endl;
    
    // 5. 最小覆盖子串演示
    cout << "5. 最小覆盖子串:" << endl;
    string s1 = "ADOBECODEBANC";
    string t1 = "ABC";
    MinimumWindowSubstring minWindow;
    string resultStr = minWindow.minWindow(s1, t1);
    cout << "字符串: \"" << s1 << "\"" << endl;
    cout << "目标: \"" << t1 << "\"" << endl;
    cout << "最小覆盖子串: \"" << resultStr << "\"" << endl << endl;
    
    // 6. 三数之和演示
    cout << "6. 三数之和:" << endl;
    vector<int> nums3 = {-1, 0, 1, 2, -1, -4};
    ThreeSum threeSum;
    vector<vector<int>> result3 = threeSum.threeSum(nums3);
    cout << "数组: [-1, 0, 1, 2, -1, -4]" << endl;
    cout << "三数之和为0的组合:" << endl;
    for (const auto& triplet : result3) {
        cout << "[" << triplet[0] << ", " << triplet[1] << ", " << triplet[2] << "]" << endl;
    }
}

int main() {
    demonstrateTwoPointers();
    return 0;
}
